1. Field of the Invention
The present invention relates to a design for universally testable logic elements useful in forming logic circuits and to a method for detecting faults in such logic circuits in order to do rapid testing of integrated circuits, logic boards and logic-based digital computing systems.
2. Description of the Prior Art
Very large-scale integrated circuits consist of many logic elements which are accessed by a relative small number of input/output ("I/O") pins. The manufacture testing of these devices has the objective of separating properly operating units from those which do not function properly. This task is a difficult one, and an increasing fraction of the unit device cost is required for manufacture testing.
When many integrated circuits are placed on a logic board, this assembly must also be tested. In this case, a determination is first required of whether or not the board works properly. If a malfunction is indicated, then the source of the problem must be diagnosed accurately to the "least replaceable unit" (usually one integrated circuit). When many logic boards are assembled as a logic system, occasional diagnostics are run to assure proper operation or locate failed components. At all three levels--integrated circuit, logic board, and system--rapid testing and diagnostic information is a desirable characteristic.
The testing described above involves the application of test patterns to inputs, the observation of output responses, and the comparison of these outputs with known good values. Patterns and expected responses can be generated based on the intended function (or operation) of the logic circuit, in which case the testing is described as functional testing. On the other hand, test patterns can be generated based upon the known design structure and expected device failure models; this type of testing is known as structural testing. Various combinations of functional and structural testing have been used in the logic testing art.
Because of the difficulty of determining and applying a good set of test patterns which differentiate between working and faulty logic components, numerous "design for testability" methodologies have been proposed and implemented. Each of these constrains or modifies designs so that the resulting logic circuitry is easier to test.
A summary of existing design methodologies is set out in Williams, Thomas W., and Parker, Kenneth P., "Design for Testability - A Survey," IEEE Transactions on Computers, Vol. C-31, January 1982, pp. 2-15. One of the most popular current methodologies discussed therein is known generically as "scan design," or "Level Sensitive Scan Design," as disclosed in U.S. Pat. No. 3,761,695. This design for testing methodology allows the test generation problem in sequential circuits to be reduced to one of generating tests for combinational logic. This is accomplished by adding shift registers to the logic design to load a test sequence (by shifting in the circuit state) and unload the circuit's signal response to such data sequence (by scanning out the circuit state). Numerous improvements to this popular design have been developed. They include U.S. Pat. Nos. 4,225,957; 4,224,048; and 4,357,703; and the following IBM Technical Disclosure Bulletins: Vol. 13, No. 51, pp. 1093-1094; Vol. 20, No. 10, pp. 4021-4022; Vol. 25, No. 10, pp. 5124-5127.
The technical literature contains a few publications on the concept of "function-independent" or "structural" digital network testing. For this class of "design for testability" methodology, a set of structural faults is postulated, and circuits are designed in such a way that the applied test set (which is usually quite small) effectively detects all such (stuck-at) faults--independent of the intended functional operation of the particular logic network. This is possible because these circuits have special "test modes" in addition to the "normal mode" of operation. A recent publication in this area is "Dual-Mode Logic for Function Independent Fault Testing" by Sumit Dasgupta, Carlos R. P. Hartmann, and Luther D. Rudolph in the IEEE Transactions on Computers, November 1980, pp. 1025-1029. This publication, however, discloses only a theoretical circuit which requires at least four "control" inputs in addition to the usual data inputs for detecting single stuck-at faults with at least two test patterns. The publication also sets out a theoretical proof that a sequential logic network can be constructed to detect all single stuck-at faults and data input faults with at least six test patterns but only if the network has at least five control inputs. No practical realizations of such a theoretical circuit were suggested.
A publication entitled "Total Stuck-at-Fault Testing by Circuit Transformation" by A. S. La Paugh and R. J. Lipton in the Proceedings of the IEEE 20th Design Automation Conference, 1983, pp. 713-716, proposes a "structural testing" approach to the production testing of VLSI which is actually the combination of three techniques which would be used independently. First, the author suggests using a special class of combinational circuits called "bipartite circuits" for designing the circuits. Bipartite circuits are circuits which have their essential parts duplicated so long as all the circuits consist solely of NOR and NAND gates. The author uses a color-coded wiring technique to test to determine if a circuit is bipartite or to convert a non-bipartite circuit into a bipartite one. Secondly, the author suggests using a NMOS controllable gate with the "bipartite" circuit. Thirdly, the author suggests adding observational logic to observe the events that will occur at the internal nodes of the circuit.
All function-independent methodologies proposed to date have been of only academic value because their complexity and the associated design overhead (silicon area consumption) renders them far from economically viable.
The first conceptual steps toward a realistic and economical, function-independent methodology are described in my Ph.D. dissertation, Digital Design for Testability and Concurrent Fault Detection in LSI and VLSI Devices, The University of Texas at Austin, August 1980. The dissertation describes a theoretical universally testable logic element which has the ability to detect all classical stuck-at-zero and stuck-at-one faults in arbitrary combinational circuits. Extensions of the concepts to sequential circuits are also discussed. However, the logic elements are described only functionally, and no practical realizations for the logic elements are presented or suggested. In fact, it can be shown that, using traditional logic gates, no realization of such a logic element is possible which preserves the desirable property of allowing the detection of all gate input and output stuck-at-one and zero faults.